package day_2022_7_to_8.day48;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author haomin
 * @date 2022/08/29 10:34
 **/
public class Day44_2_Offer03_FindRepeatNumber {
    class Solution1 {
        public int findRepeatNumber(int[] nums) {
            Arrays.sort(nums);
            for(int i = 0; i < nums.length-1; ++i){
                if(nums[i] == nums[i+1]){
                    return nums[i];
                }
            }
            return -1;
        }
    }
    class Solution2 {
        public int findRepeatNumber(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            for(int num : nums){
                if(map.containsKey(num)) return num;
                map.put(num, 1);
            }
            return -1;
        }
    }
    class Solution3 {
        public int findRepeatNumber(int[] nums) {
            int[] arr = new int[nums.length];
            for(int num : nums){
                arr[num]++;
                if(arr[num] > 1) return num;
            }
            return -1;
        }
    }
    class Solution {
        public int findRepeatNumber(int[] nums) {
            int i = 0;
            while (true) {
                int m = nums[i];
                int n = nums[m];
                if (m == i) {
                    ++i;
                } else if (n == m) {
                    return m;
                } else {
                    nums[m] = m;
                    nums[i] = n;
                }
            }

        }
    }
}